package com.liunian.algorithmstudy.str;

public class LongestPalindrome5 {

    // 1. 动态规划
    public String longestPalindrome1(String s) {
        int n = s.length();
        if (s == null || n <= 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        int maxLen = 1;
        int left = 0;
        boolean[][] dp = new boolean[n][n];
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (len == 1) {
                    dp[i][j] = true;
                } else if (len == 2) {
                    dp[i][j] = (chars[i] == chars[j]);
                } else {
                    dp[i][j] = (chars[i] == chars[j] && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                    left = i;
                }
            }
        }
        return new String(chars, left, maxLen);
    }

    // 2. 中心扩散
    public String longestPalindrome2(String s) {
        int n = s.length();
        if (s == null || n <= 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        int maxLen = 1;
        int left = 0;
        for (int i = 0; i < n; i++) {
            int len1 = getPalindromeLen(chars, i, i);
            int len2 = getPalindromeLen(chars, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                left = i - (len - 1) / 2;
            }
        }
        return new String(chars, left, maxLen);
    }

    private int getPalindromeLen(char[] chars, int left, int right) {
        while (left > 0 && right < chars.length && chars[left] == chars[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    // 2. manacher算法：在线性时间内查找字符串中任意位置开始的所有回文子串。
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        char[] newChars = proPrecess(chars);
        int center = 0;
        int right = 0;
        int n = newChars.length;
        int[] results = new int[n];
        for (int i = 1; i < n - 1; i++) {
            // 选定当前中心位置center及有边界right，以中心位置计算i的镜像i_mirror的位置。
            int i_mirror = 2 * center - i;
            // 如果i不超过右边界，results[i] 取right - i与results[i_mirror]的最小值
            if (i < right) {
                results[i] = Math.min(right - i, results[i_mirror]);
            }
            // 以i为中心，results[i]为半径再扩展比对，并更新results[i]和right
            while (newChars[i + 1 + results[i]] == newChars[i - 1 - results[i]]) {
                results[i]++;
            }
            // 如果i+results[i]超过右边界，更新center和right
            if (i + results[i] > right) {
                center = i;
                right = i + results[i];
            }
        }

        // 遍历results找到最大的回文半径
        int maxR = 0;
        int index = 0;
        for (int j = 1; j < n - 1; j++) {
            if (results[j] > maxR) {
                maxR = results[j];
                index = j;
            }
        }
        int left = (index - maxR) / 2;
        return new String(chars, left, maxR);
    }

    private char[] proPrecess(char[] chars) {
        char[] newChars = new char[2 * chars.length + 3];
        newChars[0] = '^';
        newChars[newChars.length - 1] = '$';
        newChars[newChars.length - 2] = '#';
        for (int i = 0; i < chars.length; i++) {
            newChars[2 * i + 1] = '#';
            newChars[2 * (i + 1)] = chars[i];
        }
        return newChars;
    }

    public static void main(String[] args) {
        LongestPalindrome5 palindrome = new LongestPalindrome5();
        System.out.println(palindrome.longestPalindrome("bb"));
    }
}
